#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;   //定义数据元素类型

typedef struct DuLNode{     //双向链表结点类型
    ElemType data;  //数据域
    struct DuLNode *prior,*next;//前驱指针和后继指针
}DuLNode,*DuLinkList;//双向链表类型

//获取双向链表中第i个结点的指针
DuLinkList GetElem_DulL(DuLinkList L, int i){
    if (i < 1){
        return NULL;//位置i不合法
    }
    DuLinkList p = L->next;//p指向第1个结点
    int j = 1;//j记录当前结点的位置
    while (p != L && j < i){
        p = p->next;//指向下一个结点
        j++;//位置加1
    }
    if (p == L) {
        return NULL; // 位置i超出链表长度
    }
    return p;//返回第i个结点的指针
}

//创建一个带头结点的空双向链表
DuLinkList CreateList_Dul(){
    DuLinkList L = (DuLinkList)malloc(sizeof(DuLNode)); //创建头结点
    if (L == NULL){ //存储分配失败
        return NULL;//返回空指针
    }
    L->prior = L;//头结点的前驱指针指向自己
    L->next = L;//头结点的后继指针指向自己
    return L;//返回头结点指针
}

//删除位置i的结点
int ListDelete_DuL(DuLinkList *L, int i, ElemType *e){
    DuLinkList p = GetElem_DulL(*L, i);//获取第i个结点的指针
    if (p == NULL){
        return 0;//第i个结点不存在
    }
    
    *e = p->data; //保存被删除结点的数据
    
    //修改前驱结点的后继指针
    p->prior->next = p->next;
    //修改后继结点的前驱指针
    p->next->prior = p->prior;
    
    free(p); //释放被删除结点的内存
    return 1;//删除成功
}

//在链表头部插入元素（用于测试）
int InsertAtHead(DuLinkList *L, ElemType e){
    DuLinkList s = (DuLinkList)malloc(sizeof(DuLNode));
    if (s == NULL){
        return 0;//存储分配失败
    }
    
    s->data = e;
    s->next = (*L)->next;
    s->prior = *L;
    (*L)->next->prior = s;
    (*L)->next = s;
    
    return 1;
}

//打印双向链表
void PrintList_DuL(DuLinkList L){
    DuLinkList p = L->next;//p指向第1个结点
    printf("链表内容: ");
    while (p != L){
        printf("%d ", p->data);//打印当前结点的数据元素
        p = p->next;//指向下一个结点
    }
    printf("\n");
}

int main(){
    DuLinkList L = CreateList_Dul();//创建空双向链表
    
    //插入一些测试数据
    InsertAtHead(&L, 30);
    InsertAtHead(&L, 20);
    InsertAtHead(&L, 10);
    
    printf("初始链表:\n");
    PrintList_DuL(L);
    
    ElemType deletedElem;
    
    //删除位置2的结点
    if (ListDelete_DuL(&L, 2, &deletedElem)){
        printf("删除位置2的元素: %d\n", deletedElem);
        PrintList_DuL(L);
    }
    
    //删除位置1的结点
    if (ListDelete_DuL(&L, 1, &deletedElem)){
        printf("删除位置1的元素: %d\n", deletedElem);
        PrintList_DuL(L);
    }
    
    //尝试删除不存在的结点
    if (!ListDelete_DuL(&L, 5, &deletedElem)){
        printf("删除位置5失败，该位置不存在\n");
    }
    
    return 0;
}